package leetcode.Hot100;

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * @author Cheng Jun
 * Description: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * <p>
 * n == height.length
 * 1 <= n <= 2 * 104
 * 0 <= height[i] <= 105
 * @version 1.0
 * @date 2021/12/20 19:54
 * 经典题 二刷 必做题 字节面试题
 */
public class trap {
    public static void main(String[] args) {
        trap1(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }

    // 只有洼地，才能接住水。所以我们要找洼地，数组具有什么的特征才能构成洼地，
    // 显然单调递增不行，单调递减也不行，递增或递减的数组，水会全部流走。
    // 洼地的特征必须是 先单调递减 然后单调增
    //  |
    //  |           |
    //  |   |   .   |
    //  [3, 1,  0, 2]
    // 那么，我们必然要维护一个 单调递减栈，当出现 后续数组元素 bigger 大于栈顶元素时，就会出现洼地
    // 出现洼地以后，我们要明确洼地的两端的较短边，所以  bigger 与栈底元素比较，决定较短边。
    // 从上述分析来看，我们需要使用双端队列更合适。
    // 如果 栈底元素 大于 bigger，那么计算所有构成洼地的面积，然后“抹平”洼地
    // 如果 栈底元素 小于等于 bigger，计算所有构成 洼地的面积，然后 “丢弃” 洼地。
    static int trap(int[] height) {
        // 数组长度
        int n = height.length;
        // 区域面积初始化
        int area = 0;
        // 保存边长的 双端队列
        Deque<Integer> sideDeque = new LinkedList<>();
        // 条件中 height.length >= 1
        sideDeque.add(height[0]);
        for (int i = 1; i < height.length; i++) {
            int lastSide = sideDeque.peekLast();
            // height[i] 更小，直接入栈，反之则会出现洼地
            if (height[i] <= lastSide) {
                sideDeque.addLast(height[i]);
            } else {
                int fistSide = sideDeque.peekFirst();
                // 左侧大，计算并抹平
                if (fistSide > height[i]) {
                    ListIterator<Integer> iterator = (ListIterator) sideDeque.iterator();
                    while (iterator.hasNext()) {
                        int side = iterator.next();
                        if (side < height[i]) {
                            // 注意每个柱子形成的洼地，只计算各自的垂直方向面积， 宽一直是 1，故省略
                            area += height[i] - side;
                            // 抹平洼地
                            iterator.set(height[i]);
                        }
                    }
                } else {
                    // 右侧大，计算并舍弃
                    // desIterator 从后向前的迭代器
                    Iterator<Integer> desIterator = sideDeque.descendingIterator();
                    while (desIterator.hasNext()) {
                        int side = desIterator.next();
                        area += fistSide - side;
                        desIterator.remove();
                    }
                }
                // 无论是抹平洼地，还是舍弃洼地，最后元素都要入栈
                sideDeque.addLast(height[i]);
            }
        }
        return area;
    }


    //  |
    //  |           |
    //  |   |   .   |
    //  [3, 1,  0, 2]
    //  求出每个位置的左边最大值 leftMax 和 右边最大值 rightMax，取两者的较小值，然后与当前位置作差，就是当前位置的面积
    //  求每个位置的 leftMax 和 rightMax 可以遍历整个数组，但是每次都遍历就会让时间复杂度变成 O(n^2)
    //  这里我们使用dp 找出每个位置的leftMax 和 rightMax
    static int trap1(int[] height) {
        int area = 0;
        int n = height.length;
        if (n <= 2) {
            return area;
        }
        // 每个位置对应的左边最大值，右边最大值
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        // 初始化
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        // 动态转移方程：
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = height[i] > leftMax[i - 1] ? height[i] : leftMax[i - 1];
        }
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = height[i] > rightMax[i + 1] ? height[i] : rightMax[i + 1];
        }
        for (int i = 0; i < height.length; i++) {
            area += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return area;
    }

    // todo 双指针解法
}
